Educational Codeforces Round 47

比赛

http://codeforces.com/contest/1009

总结：codeforces比赛打得挺少，这次有几个问题，一是时间分配，二是心态。T3后来在比赛结束一分钟左右敲好了，但事后想起来因为太紧张导致好几次提交错误，浪费时间。还有因为是英文题面，不能像中文题面那样很快地来回反复找信息，在预览题目时忽略了部分信息导致我对题目难度预估出错，在T2上花了大量的时间后才意识到T3是水题。

A. Game Shopping

题意不想放。。傻题，两个指针从左到右就好了。

B. Minimum Ternary String

题意：有一个三进制的字符串由 ‘0’ ，’1’， ‘2’ 组成。我们每次可以交换相邻的两个字符的条件是这两个为 ‘0’, ‘1’ 或为 ‘1’, ‘2’。
求该字符串的最小字典序。例如，201 的最小字典序为 120。

被题目绕了差不多一个小时？。。。。。总时间只有2小时啊。。。。。
这种贪心题目容易产生很多具有误导性的错误贪心算法，一开始我想的是找到连续的一个块由 ‘0’, ‘1’ 组成或 ‘1’, ‘2’ 组成，将块里所有较小的字符归到左边，较大的字符归到右边。

这题还有一个坑点就是，如果不找到正确贪心算法，那么思考时，区间会被多次进行找块、换位的操作，这个弯绕不过去，这应该也是多数贪心具有的特点。我根据一开始的想法写，多次区间的操作这点达不到，就wa了。。。

正解非常优美，发现 1 畅通无阻，可以任意移动，0 和 2 不可能交换相对位置，例如 0 在 2 前面，那么就不可能通过移动达到 0 在 2 后面。

为了达到字典序最小，第一个 2 前的 0 们应该移到最前面，所有的 1 都要移到第一个 2 前面，第一个 2 前面的 0 们的后面，第一个 2 后面的 0 和 2 保持不变。

然后，要注意整个序列没有 2 的情况。

结果，知道算法还写挂了。。。。被 hack 的感觉就是这样的吗？（因为我判断，如果序列里有 2 ，就在输出第一个 2 前面的元素后输出一个 2。有无 2 都从第一个 2 的位置（如果没有就是 n）开始 for 到 n，输出所有不是 1 的元素，但如果序列里没有 2，n 的位置上又是 0，岂不是多输了一个 0。）

C. Annoying Present

题意：一个长度为 n 的数组（初始全为0），进行 m 次操作。
操作：给你 m 个 x、d，你任意挑选一个 i (1~n)，每个数字加上 x + |i - j| * d（ j 表示对应数字的下标）
问 m 次操作后的最大算术平均值为多少？

水题，一看就有想法（。。。）首先每个位置的数组都应加上 $\sum_{i = 1}^n x_i$ ，然后考虑 1 ～ m 的 d，若 < 0 ，那么只能对整个序列的平均值产生不好的影响，我们应该把这种影响降到最低，也就是 $d * (\sum_{j = 1}^n |pos - j|)$ 最小，那么 pos 肯定是越靠中间越好，即 n 或 1；若 d > 0 ，那么肯定 pos 越靠两边越好。提前记录 n 到每个位置的距离和与 (n + 1) / 2 到每个位置的距离和即可。注意 long long。

D. Relatively Prime Graph

题意：构造一个 n 个点 m 条边的图，要求：图联通，GCD(u，v) = 1， u 、 v之间才可以建边。节点分别为 1 ～ n。

由欧拉函数表 $\phi(n)$ 可得，573以内互质的对数就已经超过 1e5 了，暴力枚举即可。

首先 1 到任何点都可以连一条边，这样就能保证图连通了。接着再根据上面的结论，确定该算法不会超时。

当然这需要足够的数感和估算技巧(?)

CODE：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
int n, m;
vector<pii> ans;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n && ans.size() < m; i++)
        for (int j = i + 1; j <= n && ans.size() < m; j++)
            if (__gcd(i, j) == 1)
                ans.push_back(make_pair(i, j));
    if (m < n - 1 || ans.size() < m) {
        printf("Impossible\n");
    } else {
        printf("Possible\n");
        for (int i = 0; i < (int)ans.size(); i++)
            printf("%d %d\n", ans[i].first, ans[i].second);
    }
    return 0;
}

E. Intercity Travelling

题意：Leha从数轴的 0 到 n ，中间的整数点都有可能有休息点也可能没有休息点。当你连续坐 k 站时，每两站间的疲劳值为 a1, a2 …… ak，如果第 k 站有休息点，那么你可以在此处休息，然后接下来的站点的疲劳值又从 a1 开始，否则继续为 ak + 1。题目给你 n 和 ai，每个站点有休息点的概率都是 1/2，问你期望值 * 2 ^ (n - 1) 的值。

我们知道从 0 到 1 的疲劳值必定为 a1，从 1 到 2 的疲劳值为 a1(1 / 2) 或 a2(1 / 2) ，从 2 到 3 的疲劳值为 a1(1 / 2) , a2(1 / 4),